/*树套数
* 1.树套树
    一棵树套着另一棵树 线段树套平衡树、权值线段树套线段树等


* 2.每一个线段树节点内再多存储一个multiset，表示这个区间内的平衡树

*/

// #define DEBUG
// #pragma GCC optimize("O1,O2,O3,Ofast")
// #pragma GCC optimize("no-stack-protector,unroint-loops,fast-math,inline")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <cstdio>
#include <cmath>
using namespace std;
const int N=2000010, INF=2147483647;

inline int read(){
	int x=0;
	bool f=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return f?-x:x;
}

struct AvlNode{
    int s[2], pa, v; //左右节点id 父节点id 当前点权值
    int size; //以当前节点为根的子树中节点的总数

    void init(int _v, int _pa) //初始化节点
    {
        s[0]=s[1]=0;
        v = _v, pa = _pa;
        size = 1;
    }
} avl[N]; //平衡树 内层树
int idx;

struct SegNode{
    int l, r;
    int root; //区间[l,r]对应平衡树的根节点
} Segtree[N]; //线段树 外层树
int n, m;
int w[N];

inline void pushup(int u)//维护子树大小,更新节点u的size
{  
    avl[u].size=avl[avl[u].s[0]].size + avl[avl[u].s[1]].size+1;
}

inline void rotate(int x)  //旋转 x上移一层
{
    int y=avl[x].pa, z=avl[y].pa; //父节点 祖父节点
    bool k=avl[y].s[1]==x; //x是否是父节点的子节点
    //交换x，y
    avl[z].s[avl[z].s[1]==y]=x; 
    avl[x].pa=z; 

    //将x的孩子节点接到y上
    avl[y].s[k]=avl[x].s[k^1], avl[avl[x].s[k^1]].pa=y;

    avl[x].s[k^1]=y, avl[y].pa=x;
    pushup(y), pushup(x);
}

inline void splay(int &root, int x,int k)//将x转到k下面
{ 
    while(avl[x].pa != k)
    {
        int y=avl[x].pa, z=avl[y].pa;
        if(z!=k)
        {
            if((avl[y].s[1]==x)^(avl[z].s[1]==y)) //不在一条直线上
                rotate(x);
            else
                rotate(y);
        }
        //此时x，x的父节点，x的祖父节点一定在一条直线上
        rotate(x);
    }
    if(!k) //x为根节点
        root=x;
}

inline void insert(int &root, int v) //加点(参数为权值)
{ 
    int u=root, pa=0; //
    while(u) //找到v的插入位置
        pa=u, u=avl[u].s[v>avl[u].v];
    u=++idx;
    if(pa) avl[pa].s[v>avl[pa].v]=u;
    avl[u].init(v, pa);
    splay(root, u, 0); //将新插入节点旋转至根节点
}

inline int get_x(int root, int v) //平衡树(内层数) 找出 < k 的数的个数
{
    int u=root;
    int res=0;
    while(u)
    {
        if(avl[u].v<v) //在右侧
            res += avl[avl[u].s[0]].size+1, u=avl[u].s[1];
        else  u=avl[u].s[0]; //在左侧
    }
    return res;
}

inline void avl_modify(int &root, int pos, int x) //将pos改为x
{
    // printf("avl_modify: %d %d %d\n", root, pos, x);
    int u=root;
    while(u)
    {
        if(avl[u].v==pos) break;
        if(avl[u].v<pos) u=avl[u].s[1];
        else u=avl[u].s[0];
    }
    splay(root, u, 0);
    //printf("splay1\n");
    int l=avl[u].s[0], r=avl[u].s[1];
    while(avl[l].s[1]) l=avl[l].s[1];
    while(avl[r].s[0]) r=avl[r].s[0];
    splay(root, l, 0), splay(root, r, l); //将p的前驱和后继旋转上来
    //printf("splay2\n");

    avl[r].s[0]=0; //删掉pos
    pushup(r), pushup(l);
    insert(root, x);
    // printf("avl_modify: %d %d %d\n", root, pos, x);
}

inline int get_pre(int root, int v) //平衡树 找到<v的最大值
{
    int u=root, res=-INF;
    while(u)
    {
        if(avl[u].v<v) 
            res = max(res, avl[u].v), u=avl[u].s[1];
        else  u=avl[u].s[0];
    }
    return res;
}

inline int get_next(int root, int v) //平衡树 找到<v的最大值
{
    int u=root, res=INF;
    while(u)
    {
        if(avl[u].v>v) 
            res = min(res, avl[u].v), u=avl[u].s[0];
        else  u=avl[u].s[1]; 
    }
    return res;
}

void build(int u, int l, int r) //线段树
{
    Segtree[u]={l, r};
    insert(Segtree[u].root, -INF), insert(Segtree[u].root, INF);
    for(int i=l; i<=r; i++) insert(Segtree[u].root, w[i]); //将当前区间内的所有数插入对应的平衡树中
    if(l==r) return; //区间叶节点
    int mid=l+r>>1;
    build(u<<1, l, mid);
    build(u<<1|1, mid+1, r);
}

void modify(int u, int pos, int x)
{
    avl_modify(Segtree[u].root, w[pos], x); //删掉pos的数据，插入x
    if(Segtree[u].l == Segtree[u].r) return;

    int mid=Segtree[u].l+Segtree[u].r>>1;
    if(pos<=mid) modify(u<<1, pos, x);
    else modify(u<<1|1, pos, x);

}

int query_rank_by_val(int u, int l, int r, int val) //线段树 [l, r]中<val数的个数
{
    if(l <= Segtree[u].l && Segtree[u].r <= r) return get_x(Segtree[u].root, val)-1; //左哨兵
    int mid=Segtree[u].l+Segtree[u].r>>1;
    int ans=0;

    if(l<=mid) ans+=query_rank_by_val(u<<1, l, r, val);
    if(r>mid) ans+=query_rank_by_val(u<<1|1, l, r, val);
    return ans;
}

int query_pre(int u, int l, int r, int x) //节点id 查询区间 x
{
    if(l <= Segtree[u].l && Segtree[u].r <= r) { //转为单节点的平衡树的树内访问
        return get_pre(Segtree[u].root, x);
    }
    int mid=Segtree[u].l+Segtree[u].r>>1;
    int ans=-INF;
    if(l<=mid) ans=max(ans, query_pre(u<<1, l, r, x));
    if(r>mid) ans=max(ans, query_pre(u<<1|1, l, r, x));
    return ans;
}

int query_post(int u, int l, int r, int x) //节点id 查询区间 x
{
    if(l <= Segtree[u].l && Segtree[u].r <= r) { //转为单节点的平衡树的树内访问
        return get_next(Segtree[u].root, x);
    }
    int mid=Segtree[u].l+Segtree[u].r>>1;
    int ans=INF;
    if(l<=mid) ans=min(ans, query_post(u<<1, l, r, x));
    if(r>mid) ans=min(ans, query_post(u<<1|1, l, r, x));
    return ans;
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt","r",stdin);
        freopen("./out.txt","w",stdout);
    #endif
    
    scanf("%d%d", &n, &m);
    // n=read(); m=read();
    for(int i=1; i<=n; i++) scanf("%d", &w[i]);
    build(1, 1, n);
    while(m--)
    {
        int op, l, r, pos, x;
        scanf("%d", &op);
        // op=read();
        //printf("op:%d %d %d\n", op, l, r);
        if(op == 1) //val->rank
        {
            scanf("%d%d%d", &l, &r, &x);
            // l=read(); r=read(); x=read();
            printf("%d\n", query_rank_by_val(1, l, r, x)+1);
        }
        else if(op==2) { //rank->val
            scanf("%d%d%d", &l, &r, &x);
            // l=read(); r=read(); x=read();
            int L=0, R=1e8;
            while(L<R)
            {
                int mid=L+R+1>>1;
                //printf("l r mid %d %d %d\n", l, r, mid);
                if(query_rank_by_val(1, l, r, mid)+1<=x) L=mid;
                else R=mid-1;
            }
            printf("%d\n", R);
        }
        else if(op==3) {
            scanf("%d%d", &pos, &x);
            // pos=read(); x=read();
            modify(1, pos, x);
            w[pos]=x;
        }        
        else if(op==4) { // l r x
            // l=read(); r=read(); x=read();
            scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", query_pre(1, l, r, x));
        }
        else if(op==5) { // l r x
            // l=read(); r=read(); x=read();
            scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", query_post(1, l, r, x));
        }
    }
    return 0;
}